/*
给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

// 如果有环，那么在没有终点的跑圈中，跑得快的终会再次相逢跑得慢的 (不论他们各自的速度是多少,不要理性思考,想想生活实景,跑得快的人总是会“超圈”跑得慢的人, "超圈"的那一瞬间就是相逢的时刻, 不论他们每个人的步调是怎样的, )

/* todo 一定是 2倍关系吗？
假设两人速度分别为v1、v2, n为迭代次数, r1、r2为两人分别跑的圈数, k为重逢时所处的循环节中的第x个节点
v1、v2、r1、r2、n、k都为正整数

v1 * n = k * r1
v2 * n = k * r2

v1!=v2 求证是不是总是存在正整数n使得正整数k有任意正整数解？

v1、v2、k 是全称量词（任意）
r1、r2和n是存在量词（存在）

那么我们可以假设存在量词n为1
那么v1只要等于 v2r1/r2 且为整数即可
那么只要 r1/r2 = v2/v1 即可
而这个等式是一定能够成立的 （v2、v1为全程量词，r2、r1为存在量词）
故证实 v1、v2、r1、r2、n、k都为正整数 且v1!=v2 时 总是存在正整数n使得正整数k有任意正整数解

*/

const hasCycle = (head)=>{
  let p1 = head; //快指针
  let p2 = head; //慢指针
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) {
      return true;
    }
  }

  return false;
}

//时间复杂度：O(N)O(N)，其中 NN 是链表中的节点数。
//  + 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
//  + 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。
//空间复杂度：O(1)。我们只使用了两个指针的额外空间。
